package com.cet.algorithm.哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: algorithm
 * @description:
 * @author: 陈恩涛
 * @create: 2022-03-13 16:36
 **/
public class LC438 {

    public static List<Integer> findAnagrams(String s, String p) {
        int[] alphabetCounter = new int[26];
        for (int i = 0; i < p.length(); i++) {
            alphabetCounter[p.charAt(i) - 'a']++;
        }
        List<Integer> result = new ArrayList<>();
        int pLength = p.length();
        for (int i = 0; i + pLength <= s.length(); i++) {
            int[] temp = new int[26];
            for (int j = 0; j < 26; j++) {
                temp[j] = alphabetCounter[j];
            }
            String subString = s.substring(i, i + pLength);
            for (int j = 0; j < pLength; j++) {
                temp[subString.charAt(j) - 'a']--;
            }
            boolean flag = true;
            for (int item : temp) {
                if (item != 0) {
                    flag = false;
                }
            }
            if (flag) {
                result.add(i);
            }
        }
        return result;
    }

    /**
     * 滑动窗口法
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams2(String s, String p) {
        int sLength = s.length();
        int pLength = p.length();
        int slowIndex = 0;
        List<Integer> result = new ArrayList<>();

        if (sLength < pLength) {
            return result;
        }

        int[] alphabetCounter = new int[26];
        int[] alphabetCounterP = new int[26];

        for (int i = 0; i < p.length(); i++) {
            alphabetCounterP[p.charAt(i) - 'a']++;
            alphabetCounter[s.charAt(i) - 'a']++;
        }

        for (int fastIndex = pLength; fastIndex < sLength; fastIndex++) {
            if (Arrays.equals(alphabetCounter, alphabetCounterP)) {
                result.add(slowIndex);
            }
            alphabetCounter[s.charAt(fastIndex) - 'a']++;
            alphabetCounter[s.charAt(slowIndex++) - 'a']--;
        }

        if (Arrays.equals(alphabetCounter, alphabetCounterP)) {
            result.add(slowIndex);
        }
        return result;
    }


        public static void main(String[] args) {
        System.out.println(findAnagrams2("abab", "ab"));
    }
}
